class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param head ListNode类 the head node
     * @return ListNode类
     */
    ListNode* sortInList(ListNode* head) {
        // write code here
        int len = 0;
        ListNode *cur = head;
        while (cur) 
        {
            len++;
            cur = cur->next;
        }
        return mergeList(head, len);
    }
    ListNode* mergeList(ListNode* head, int len)
    {
        if (len == 1) return head;
        int halflen = len / 2;
        ListNode *cur = head;
        for (int i = 0; i < halflen - 1; i++) cur = cur->next; // 边界情况
        ListNode *next = cur->next;
        cur->next = nullptr;
        return merge(mergeList(head, halflen), mergeList(next, len - halflen));
    }
    ListNode* merge(ListNode* p1, ListNode* p2)
    {
        ListNode newnode(0);
        ListNode* tail = &newnode;
        while (p1 && p2)
        {
            if (p1->val < p2->val)
            {
                tail->next = p1;
                p1 = p1->next;
            }
            else
            {
                tail->next = p2;
                p2 = p2->next;
            }
            tail = tail->next;
        }
        tail->next = p1 == nullptr ? p2 : p1;
        return newnode.next;
    }
};